package com.leetcode.partition7;

/**
 * @author `RKC`
 * @date 2021/12/22 9:08
 */
public class LC686重复叠加字符串匹配 {

    public static void main(String[] args) {
        System.out.println(repeatedStringMatch("aaaaaaaaaaaaaaaaaaaaaab", "ba"));
//        System.out.println(repeatedStringMatch("abcd", "cdabcdab"));
    }

    public static int repeatedStringMatch(String a, String b) {
        int[] next = new int[b.length()];
        for (int i = 1, j = 0; i < b.length(); i++) {
            while (j > 0 && b.charAt(i) != b.charAt(j)) j = next[j - 1];
            if (b.charAt(i) == b.charAt(j)) j++;
            next[i] = j;
        }
        StringBuilder sb = new StringBuilder(a);
        int repeated = 1, answer = 1;
        while (sb.length() < b.length()) {
            repeated++;
            sb.append(a);
        }
        while (kmp(sb.toString(), b, next) == -1) {
            sb.append(a);
            if (answer++ == repeated + 1) return -1;
        }
        return answer + repeated - 1;
    }

    private static int kmp(String a, String b, int[] next) {
        if (a.length() < b.length()) return -1;
        for (int i = 0, j = 0; i < a.length(); i++) {
            while (j > 0 && a.charAt(i) != b.charAt(j)) j = next[j - 1];
            if (a.charAt(i) == b.charAt(j)) j++;
            if (j == b.length()) return i + j - 1;
        }
        return -1;
    }
}
